package com.example.linkedlist;

import com.example.entity.LinkedListCustom;
import com.example.entity.LinkedNodeCustom;


/**
 * @Author: wanqian
 * @Date: 2020/8/5 14:37
 */
public class SingleLinkedListDemo {

    public static void main(String[] args) {
        LinkedNodeCustom jack = new LinkedNodeCustom(1, "Jack");
        LinkedNodeCustom tom = new LinkedNodeCustom(2, "Tom");
        LinkedNodeCustom kris = new LinkedNodeCustom(3, "Kris");
        LinkedNodeCustom matthew = new LinkedNodeCustom(4, "Matthew");

        LinkedListCustom linkedList = new LinkedListCustom();
        linkedList.addByOrder(kris);
        linkedList.addByOrder(matthew);
        linkedList.addByOrder(jack);
        linkedList.addByOrder(tom);
        System.out.println("list1为: ");
        linkedList.list();

        LinkedNodeCustom jack1 = new LinkedNodeCustom(1, "Jack1");
        LinkedNodeCustom tom1 = new LinkedNodeCustom(3, "Tom1");
        LinkedNodeCustom kris1 = new LinkedNodeCustom(4, "Kris1");
        LinkedNodeCustom matthew1 = new LinkedNodeCustom(5, "Matthew1");

        LinkedListCustom linkedList1 = new LinkedListCustom();
        linkedList1.addByOrder(kris1);
        linkedList1.addByOrder(matthew1);
        linkedList1.addByOrder(jack1);
        linkedList1.addByOrder(tom1);
        System.out.println("list2为: ");
        linkedList1.list();

        LinkedListCustom newList = combineList(linkedList, linkedList1);
        System.out.println("合并后list为: ");
        newList.list();

        //排序添加
//        linkedList.addByOrder(matthew);
//        linkedList.addByOrder(kris);
//        linkedList.addByOrder(jack);
//        linkedList.addByOrder(tom);

        //遍历
//        linkedList.list();
//        linkedList.reversePrint();

        //有效节点长度
//        linkedList.length();

        //倒数第n个节点
//        linkedList.getFromEnd(2);
//        linkedList.getFromEnd(3);

        //反转链表
//        linkedList.reverse();
//        linkedList.reverse2();
//        System.out.println("反转链表");
//        linkedList.list();

        //删除
//        System.out.println("删除3号");
//        linkedList.delete(3);
//        linkedList.list();

        //修改节点
//        System.out.println("修改2号");
//        LinkedNodeCustom Sheldon = new LinkedNodeCustom(2, "Sheldon");
//        linkedList.update(Sheldon);
//        linkedList.list();


    }

    /**
     * 合并两个有序列表
     *
     * @param list1
     * @param list2
     * @return
     */
    public static LinkedListCustom combineList(LinkedListCustom list1, LinkedListCustom list2) {
        //校验过程省略
        //创建新的链表
        LinkedListCustom list = new LinkedListCustom();
        //指针指向前一个节点
        LinkedNodeCustom pre = list.getHead();
        //两个指针指向两个链表中最小的节点，也即第一个节点
        LinkedNodeCustom node1 = list1.getHead().getNext();
        LinkedNodeCustom node2 = list2.getHead().getNext();
        //判断是否遍历完其中一个链表
        while (node1 != null && node2 != null) {
            //将pre.next指向两个链表中较小的节点
            //然后顺移较小节点的指针
            if (node1.getId() < node2.getId()) {
                pre.setNext(node1);
                node1 = node1.getNext();
            } else {
                pre.setNext(node2);
                node2 = node2.getNext();
            }
            //移动pre节点指针
            pre = pre.getNext();
        }
        //当有链表遍历完，将pre指向剩余链表的第一个节点
        if (node1 == null) {
            pre.setNext(node2);
        } else {
            pre.setNext(node1);
        }
        return list;
    }
}
